package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.LinkedListBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.ListNode;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

/**
 * find the nearest common node in a tree
 */
public class CommonNodeInLinkedList {

    public static boolean isJoinedLinkedList(ListNode listNode1, ListNode listNode2){
        ListNode endNode1 = listNode1.getNext();
        ListNode endNode2 = listNode2.getNext();
        while (endNode1.getNext()!=null){
            endNode1 = endNode1.getNext();
        }
        while(endNode2.getNext()!=null){
            endNode2 = endNode2.getNext();
        }

        return endNode2==endNode1;
    }

    public static ListNode getJoinedLinkedListNode(ListNode listNode1, ListNode listNode2){
        ListNode endNode1 = listNode1.getNext();
        ListNode endNode2 = listNode2.getNext();
        int list1Count =0,list2Count=0;
        while (endNode1.getNext()!=null){
            list1Count++;
            endNode1 = endNode1.getNext();
        }
        while(endNode2.getNext()!=null){
            list2Count++;
            endNode2 = endNode2.getNext();
        }
        if(endNode1!=endNode2){
            return null;
        }

        endNode1 = listNode1.getNext();
        endNode2 = listNode2.getNext();
        while(list1Count!=list2Count){
            if(list1Count>list2Count){
                list1Count--;
                endNode1 = endNode1.getNext();
            }
            else{
                list2Count--;
                endNode2 = endNode2.getNext();
            }
        }
        while((endNode2!=endNode1)&&(endNode2!=null||endNode1!=null)){
            endNode2=endNode2.getNext();
            endNode1 = endNode1.getNext();
        }
        if(endNode1==endNode2){
            return endNode1;
        }
        else {
            return null;
        }
    }

    public static void main(String[] args){
        ListNode listNode1 = LinkedListBuilder.buildLinkedListFromArray(new int[]{1,2,3,4,5});
        ListNode listNode2 = LinkedListBuilder.buildLinkedListFromArray(new int[]{6,5,4});
        ListNode endNode2 = listNode2.getNext().getNext();
        endNode2.setNext(listNode1.getNext().getNext().getNext());
        System.out.println("Is joined:" + isJoinedLinkedList(listNode1,listNode2));
        System.out.println("Same node value:" + getJoinedLinkedListNode(listNode1,listNode2).getValue());
    }
}
